package com.haoyang.sort;

public class A05_QuickSortDemo {

    public static void main(String[] args) {
        /**
         * 快速排序：
         *  第一轮：以0索引的数字为基准数，确定基准数在数组中正确的位置。
         *  比基准数小的全部在左边，比基准数大的全部在右边。
         *  后面以此类推
         */

        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    /**
     * 参数一: 我们要排序的数组
     * 参数二: 要排序数组的起始索引
     * 参数三: 要排序数组的结束索引
     */
    public static void quickSort(int arr[], int low, int high) {
        while (low < high) {
            // 使用三数取中法选择基准数
            int pivotIndex = medianOfThree(arr, low, high);
            int pivot = arr[pivotIndex];
            // 将基准数移到起始位置
            swap(arr, pivotIndex, low);

            // 定义两个变量记录要查找的范围
            int start = low;
            int end = high;

            // 利用循环找到要交换的数字
            while (start != end) {
                // 利用end，从后往前开始找，找比基准数小的数字
                while (start < end && arr[end] >= pivot) {
                    end--;
                }
                // 利用start，从前往后找，找比基准数大的数字
                while (start < end && arr[start] <= pivot) {
                    start++;
                }
                // 把end和start指向的元素进行交换
                if (start < end) {
                    swap(arr, start, end);
                }
            }
            // 将基准数归位
            swap(arr, low, start);

            // 优化递归，先处理较小的子数组
            if (start - low < high - start) {
                quickSort(arr, low, start - 1);
                low = start + 1;
            } else {
                quickSort(arr, start + 1, high);
                high = start - 1;
            }
        }
    }

    // 三数取中法选择基准数
    private static int medianOfThree(int arr[], int low, int high) {
        int mid = (low + high) / 2;
        if (arr[low] > arr[mid]) {
            swap(arr, low, mid);
        }
        if (arr[low] > arr[high]) {
            swap(arr, low, high);
        }
        if (arr[mid] > arr[high]) {
            swap(arr, mid, high);
        }
        return mid;
    }

    // 交换数组中的两个元素
    private static void swap(int arr[], int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}